package solution.s_3;

import java.util.*;

/**
 * 使用滑动窗口的方式
 * 其实就是将不符合条件的部分移出窗口
 */
public class Solution20200921 {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) { return 0; }

        // maxLength表示最长不重复子串的长度，p代表左指针，表示不重复子串的起始位置。
        int maxLength = 0, p = 0;
        // key：字符值，value：索引位置
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i ++) {
            char c = s.charAt(i);
            // 假如map中包含该字符并且该字符的位置是在起始位置的右边，则表示字符重复。
            if (map.containsKey(c) && map.get(c) >= p) {
                // i-p表示当次比较的最长付重复子串的长度，比较，保留最大的数据。
                maxLength = Math.max(maxLength, i - p);
                // 左指针移动到重复的位置的下一个元素的位置
                p = map.get(c) + 1;
            }
            map.put(c, i);
        }

        // 当右指针遍历结束的时候，比较一下当前的最长子串与之前的子串的长度，保留长的。
        maxLength = Math.max(maxLength, s.length() - p);
        return maxLength;
    }
}
